#include "search_algo.h"


int Search::binarySearch(std::vector<int>& nums, int target) {
    // 初始化左闭右闭区间[0,size-1]
    int i = 0;
    int j = nums.size()-1;
    while(i <= j) {
        int m = i + (j -i) / 2;
        if (nums[m] < target) {  //说明 target在区间[m+1,j]中
            i = m + 1;
        }
        else if (nums[m] > target){ //说明 target在区间[i,m-1]中
            j = m - 1;
        }
        else {
            return m;
        }

    }

    // 搜索失败，返回-1
    return -1;

}

int Search::binarySearchLCRO(std::vector<int>& nums, int target) {
    // 初始化左闭右开区间[0,size)
    int i = 0;
    int j = nums.size();
    while (i < j) {
        int m = i + (j - i) / 2;
        if (nums[m] < target) { // 说明target在区间[m+1,j)中
            i = m + 1;
        }
        else if(nums[m] > target) { // 说明target在区间[i,m)中
            j = m;
        }
        else {
            return m;
        }
    }
    // 搜索失败，返回-1
    return -1;
}

int Search::binarySearchInsertionSimple(std::vector<int>& nums, int target) {
    int i = 0;
    int j = nums.size() - 1;
    while(i <= j) {
        int m = i + (j - i) / 2;
        if (nums[m] < target) {
            i = m + 1;
        }
        else if(nums[m] < target) {
            j = m - 1;
        }
        else {
            return m; // 数组中找到target,返回插入点m
        }
    }
    return i; // 数组中没找到target,返回插入点m

}

int Search::binarySearchInsertion(std::vector<int>& nums, int target) {
    int i = 0;
    int j = nums.size() - 1; // 初始化左闭右闭区间
    while(i <= j) {
        int m = i + (j - i) / 2;
        if(nums[m] < target) {
            i = m + 1;
        }
        else if (nums[m] > target) {
            j = m - 1;
        }
        else {
            j = m - 1; // 首个小于target的元素在区间[i,m-1]中
        }
    }
    // 返回插入点i
    return i;
}

int Search::binarySearchLeftEdge(std::vector<int>& nums, int target) {
    //等价于查找target的插入点
    int i = binarySearchInsertion(nums,target);
    // 数组中可能不包含target，将会导致插入点的索引i越界，或者，元素nums[i]与target不相等
    if (i == nums.size() || nums[i] != target) {
        return -1;
    }
    // 找到target，返回索引i
    return i;
}

int Search::binarySearchRightEdge(std::vector<int>& nums, int target) {
    // 转化为查找最左一个（target + 1）
    int i = binarySearchInsertion(nums,target + 1);
    // j指向最右一个target,i指向首个大于target的元素
    int j = i - 1;
    // 未找到target，返回-1；
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    return j;
}

std::vector<int> Search::twoSumBruteForce(std::vector<int>& nums, int target) {
    std::cout << "暴力搜索" << std::endl;
    int size = nums.size();
    // 双重循环，查找相加等于target的两个值，并输出索引
    for (int i = 0;i < size - 1;i++) {
        for (int j = i + 1;j < size;j++) {
            if(nums[i] + nums[j] == target) {
                return {i,j};
            }
        }
    }
    return {};
}

std::vector<int> Search::twoSumHashTable(std::vector<int>& nums, int target) {
    std::cout << "hash辅助" << std::endl;
    int size = nums.size();
    // 辅助hash表 <数组元素，元素索引>
    std::unordered_map<int,int> dic;
    // 一层循环，每个循环在hash表中查找target-nums[i]是否在hash表中
    for (int i = 0; i < size;i++) {
        // 如果target-nums[i]在hash表中，说明存在两元素之和等于target
        // 通过dic[target-nums[i]]返回target-nums[i]的索引，另外i是其中一个元素的索引
        if(dic.find(target - nums[i]) != dic.end()) {
            return {dic[target - nums[i]],i};
        }
        // 将键值对<nums[i]，i>存入hash表中，供后续循环查找
        dic.emplace(nums[i],i);
    }
    return {};
}